package ExactMsa;

import java.util.Hashtable;



/*******************************************************************
 * Computing the exact alignment of three sequences with sum-of-pairs-score.
 * Input arguments are three sequences, a score matrix and gap costs.
 *
 * Running time O(n^k*2^k), where n is length of sequence and k is amount of sequences.
 * Space Consumption O(n^k*2^k)
 *
 * @author Paula C. Tataru, Marcus Schroeder
 *
 *****************************************************************/


public class ExactMsaThreeSequences {

	/******************************************************************
	 *  Default constructor
	 *  Computes alignment of hardcoded sequences
	 *****************************************************************/
	public ExactMsaThreeSequences(Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {


		this.scoreMatrix = scoreMatrix;
		this.gapcost = gapcost;

		startAlignment();

	}



	/******************************************************************
	 * Alternative constructor
	 * Computes alignment of three given sequences and a given score matrix
	 *****************************************************************/
	public ExactMsaThreeSequences(String s1, String s2, String s3,Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {

		this.s1 = s1;
		this.s2 = s2;
		this.s3 = s3;


		this.scoreMatrix = scoreMatrix;
		this.gapcost = gapcost;

		startAlignment();

	}




	/******************************************************************
	 * Alternative constructor
	 * Sequences are handed over in an array s
	 *****************************************************************/
	public ExactMsaThreeSequences(String[] s, Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {

		this.s1 = s[0];
		this.s2 = s[1];
		this.s3 = s[2];



		this.scoreMatrix = scoreMatrix;
		this.gapcost = gapcost;

		startAlignment();
	}


	/*****************************************************************
	 * GLOBALS
	 *****************************************************************/

	// The three sequences
	private String s1 = "aaacccaaa";
	private String s2 = "cccaaa";
	private String s3 = "aaaccc";

	private String as1 ="";
	private String as2 ="";
	private String as3 ="";


	/*****************************************************************
	 * GETTERS
	 *****************************************************************/
	public int getValueInAlignmentMatrix(int i, int j,int k) {
		return D[i][j][k];
	}

	/******************************************************************
	 *  Gapcosts
	 *****************************************************************/
	private int gapcost = -5;


	private double end_time = 0;

	/******************************************************************
	 *  The Score Matrix
	 *****************************************************************/
	private Hashtable<String,Hashtable<String,String>> scoreMatrix;





public void startAlignment(){

		double time = System.nanoTime();
		D =  new int[s1.length()+1][s2.length()+1][s3.length()+1];

		computeExactAlignment();

		traceback(s1.length(),s2.length(),s3.length());


		end_time = (System.nanoTime()-time)/1000000000;


		as1 = new StringBuffer(as1).reverse().toString();
		as2 = new StringBuffer(as2).reverse().toString();
		as3 = new StringBuffer(as3).reverse().toString();

	}

	public void printOutput(){
		System.out.println("--------------------------------------");
		System.out.println("Results:");
		System.out.println("--------------------------------------");
		System.out.println("Sequence lengths: "+s1.length()+", "+s2.length()+", "+s3.length());
		System.out.println("Taken time in s: "+end_time);
		System.out.println("Score: "+D[s1.length()][s2.length()][s3.length()]);
		System.out.println("--------------------------------------");
		System.out.println();
		System.out.println();
		System.out.println(as1);
		System.out.println(as2);
		System.out.println(as3);
		System.out.println();
	}

	
	/******************************************************************
	 *  Alignment Matrix D
	 *
	 *  Has three dimensions with size [n,m,o], where
	 *  			n is length of sequence 1,
	 *  			m is length of sequence 2,
	 *  			o is length of sequence 3,
	 *
	 *  Is intialized in complete size (n*m*o) on class initialization.
	 *****************************************************************/
	private int[][][] D;



	/******************************************************************
	 * Returns the score for two compared characters a and b
	 * Values stems from a score matrix
	 *****************************************************************/
	private int matchScore(char a,char b){

		String score = ((Hashtable<String,String>) scoreMatrix.get(""+a)).get(""+b).toString();

		return Integer.parseInt(score);

		//return Float.parseFloat(score);

	}


	/******************************************************************
	 * Compute exact alignment of three sequences.
	 *****************************************************************/
	private void computeExactAlignment(){

		int n = s1.length();
		int m = s2.length();
		int o = s3.length();



		/******************************************************
		 *  INTIALIZING THE ALIGNMENT MATRIX
		 ******************************************************/
		D[0][0][0] = 0;


		// D_s1_s2
		PairwiseGlobalAlignment d_sub = new PairwiseGlobalAlignment(scoreMatrix, s1, s2, gapcost);

		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= m; j++){

				D[i][j][0] = d_sub.getValueInAlignmentMatrix(i, j) + (i+j)*gapcost;

			}
		}


		// D_s1_s3
		d_sub = new PairwiseGlobalAlignment(scoreMatrix, s1, s3, gapcost);

		for(int i = 0; i <= n; i++){
			for(int k = 0; k <= o; k++){

				D[i][0][k] = d_sub.getValueInAlignmentMatrix(i, k) + (i+k)*gapcost;

			}
		}

		// D_s2_s3
		d_sub = new PairwiseGlobalAlignment(scoreMatrix, s2, s3, gapcost);

		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= o; k++){

				D[0][j][k] = d_sub.getValueInAlignmentMatrix(j, k) + (j+k)*gapcost;

			}
		}


		/******************************************************
		 *  FILLING THE TABLE
		 ******************************************************/

		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				for(int k = 1; k <= o; k++){


					int c_ij = matchScore(s1.charAt(i-1), s2.charAt(j-1));
					int c_ik = matchScore(s1.charAt(i-1), s3.charAt(k-1));
					int c_jk = matchScore(s2.charAt(j-1), s3.charAt(k-1));

					int d1 = D[i-1][j-1][k-1] + c_ij + c_ik + c_jk;
					int d2 = D[i-1][j-1][k] + c_ij + 2*gapcost;
					int d3 = D[i-1][j][k-1] + c_ik + 2*gapcost;
					int d4 = D[i][j-1][k-1] + c_jk + 2*gapcost;
					int d5 = D[i-1][j][k] + 2*gapcost;
					int d6 = D[i][j-1][k] + 2*gapcost;
					int d7 = D[i][j][k-1] + 2*gapcost;


					/** FINDING THE MINIMUM ENTRY **/
					D[i][j][k] = Math.min(
										Math.min(
												Math.min(d1, d2),
												Math.min(d3, d4)
										),
										Math.min(
												Math.min(d5,d6),
												d7
										)
								);

				}

			}

		}
	}


	private void traceback(int i, int j, int k){



		if(i == 0 && j == 0 && k == 0){

		}
		else{
			int c_ij = 0;
			int c_ik = 0;
			int c_jk = 0;

			if(i>0 && j >0) c_ij = matchScore(s1.charAt(i-1), s2.charAt(j-1));
			if(i>0 && k >0) c_ik = matchScore(s1.charAt(i-1), s3.charAt(k-1));
			if(k>0 && j >0) c_jk = matchScore(s2.charAt(j-1), s3.charAt(k-1));

			if((i>0 && j>0 && k>0) && D[i][j][k] == D[i-1][j-1][k-1] + c_ij + c_ik + c_jk){

					as1 = as1+s1.charAt(i-1);
					as2 = as2+s2.charAt(j-1);
					as3 = as3+s3.charAt(k-1);


					traceback(i-1,j-1,k-1);

			}
			else if((i>0 && j>0) && D[i][j][k] == D[i-1][j-1][k] + c_ij + 2*gapcost){

					as1 = as1+s1.charAt(i-1);
					as2 = as2+s2.charAt(j-1);
					as3 = as3+"-";

					traceback(i-1,j-1,k);
			}
			else if((i>0 && k>0) && D[i][j][k] == D[i-1][j][k-1] + c_ik + 2*gapcost){

					as1 = as1+s1.charAt(i-1);
					as2 = as2+"-";
					as3 = as3+s3.charAt(k-1);

					traceback(i-1,j,k-1);
			}
			else if((j>0 && k>0) && D[i][j][k] == D[i][j-1][k-1] + c_jk + 2*gapcost){

					as1 = as1+"-";
					as2 = as2+s2.charAt(j-1);
					as3 = as3+s3.charAt(k-1);

					traceback(i,j-1,k-1);
				}
			else if(i>0 && D[i][j][k] == D[i-1][j][k] + 2*gapcost){

					as1 = as1+s1.charAt(i-1);
					as2 = as2+"-";
					as3 = as3+"-";

					traceback(i-1,j,k);
			}
			else if(j > 0 && D[i][j][k] == D[i][j-1][k] + 2*gapcost){

					as1 = as1+"-";
					as2 = as2+s2.charAt(j-1);
					as3 = as3+"-";

					traceback(i,j-1,k);
			}
			else if( k > 0 && D[i][j][k] == D[i][j][k-1] + 2*gapcost){

					as1 = as1+"-";
					as2 = as2+"-";
					as3 = as3+s3.charAt(k-1);

					traceback(i,j,k-1);
			}
		}


	}





}
